class Queue {
  constructor() {
    (this.dataStore = []),
      (this.add = (t) => {
        this.dataStore.push(t);
      }),
      (this.poll = () => {
        for (var t = this.dataStore[0].code, e = 0, a = 1; a < this.dataStore.length; ++a) this.dataStore[a].code < t && (e = a);
        return this.dataStore.splice(e, 1);
      }),
      (this.front = () => this.dataStore[0]),
      (this.back = () => this.dataStore[this.dataStore.length - 1]),
      (this.empty = () => 0 == this.dataStore.length),
      (this.length = () => this.dataStore.length);
  }
}
class Node {
  constructor(element) {
    this.element = element;
    this.next = null;
  }
}
class LinkedList {
  constructor() {
    this.length = 0;
    this.head = null;
  }
  getElementAt(position) {
    if (position < 0 || position >= this.length) return null;
    let current = this.head;
    for (let i = 0; i < position; i++) {
      current = current.next;
    }
    return current;
  }
  append(element) {
    let node = new Node(element);
    if (this.head === null) this.head = node;
    else {
      let current = this.getElementAt(this.length - 1);
      current.next = node;
    }
    this.length++;
  }
  isEmpty() {
    return this.length == 0;
  }
  size() {
    return this.length;
  }
  addAll(x) {
    if (x.head != null) {
      let cur = x.head;
      while (cur != null) {
        this.append(cur.element);
        if (cur.next != null) cur = cur.next;
        else break;
      }
    }
  }
  toArray() {
    let out = [];
    let cur = this.head;
    while (cur != null) {
      out.push(cur.element);
      if (cur.next != null) cur = cur.next;
      else break;
    }
    return out;
  }
}
class Mode {
  constructor(nums, step, zero_pos) {
    this.difficulty = 3;
    this.level = 9;
    this.nums = nums;
    this.step = step;
    this.cost = 0;
    this.zero_pos = zero_pos;
    this.moved_path = new LinkedList();
  }
  setPath(x) {
    this.moved_path = new LinkedList();
    this.moved_path.addAll(x);
    return this;
  }
}
/* 工具函数 */
function arrayToString(x) {
  sb = "";
  x.forEach((k) => {
    sb = sb + k + "-";
  });
  return sb;
}
function mode_copy(x) {
  return new Mode(x.nums.slice(), x.step, x.zero_pos);
}

/* 变量设置 */
readIn = [1, 2, 3, 4, 5, 0, 7, 8, 6];
moveAble = [
  [1, 3, -1, -1],
  [0, 2, 4, -1],
  [1, 5, -1, -1],
  [0, 4, 6, -1],
  [1, 3, 5, 7],
  [2, 4, 8, -1],
  [3, 7, -1, -1],
  [4, 6, 8, -1],
  [5, 7, -1, -1],
];
mp = new Map();
que = new Queue();
goal_code = arrayToString([1, 2, 3, 4, 5, 6, 7, 8, 0]);

que.add(new Mode([1, 2, 3, 4, 5, 6, 7, 0, 8], 0, 7));
mp.set(arrayToString(readIn), true);
nowPath = new LinkedList();
// step_cnt = 0;

// cal: do {
let e = que.poll()[0];
let pos = e.zero_pos;
i = 3 - 1;
let ie = mode_copy(e);
nowPath = new LinkedList();
nowPath.addAll(e.moved_path);
console.log("Here 130", moveAble[pos]);
if (moveAble[pos][i] != -1) {
  let k1 = arrayToString(ie.nums);
  [ie.nums[pos], ie.nums[moveAble[pos][i]]] = [ie.nums[moveAble[pos][i]], ie.nums[pos]];
  let k2 = arrayToString(ie.nums);
  console.log(k1, " -> ", k2);
  nowPath.append(moveAble[pos][i]);
  let k = arrayToString(ie.nums);
  console.log(k);
  if (k == goal_code) {
    console.log("SUCC", k, nowPath.toArray());
    // break cal;
  }
  if (!mp.has(k)) {
    que.add(new Mode(ie.nums, e.step + 1, moveAble[pos][i]).setPath(nowPath));
    mp.set(k, true);
  }
}
// } while (!que.empty());

console.log(nowPath.toArray());
